import java.util.*;
/**
 * @program: leetcode004
 * @author: JCM
 * @create: 2022-11-25 10:13
 * @description: 寻找两个正序数组的中位数
 **/
public class LeetCode004 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // new 一个新数组，放置合并后的正序数组
        int[] nums = new int[nums1.length+nums2.length];
        int i = 0,j = 0;
        int k = 0;
        while(i < nums1.length && j < nums2.length) {
            //将 nums1 中的小数 先存进去
            while(i < nums1.length && nums1[i] < nums2[j]) {
                nums[k] = nums1[i];
                k++;
                i++;
            }
            //判断 nums1 中的数据是否存完
            if(i==nums1.length) break;
            while(j < nums2.length && nums2[j] <= nums1[i]) {
                nums[k] = nums2[j];
                k++;
                j++;
            }
        }
        while(i < nums1.length) {
            nums[k++] = nums1[i++];
        }
        while(j < nums2.length) {
            nums[k++] = nums2[j++];
        }
        double ret = 0;
        int index = nums.length/2;
        if(nums.length%2 == 0) {
            ret = (nums[index]+nums[index-1])/2.0;
        }else {
            ret = nums[index];
        }
        return ret;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1+len2;
        // new 一个新数组
        int[] arr = new int[len];
        // 先不进行比较，直接将所有数据存放到新数组中
        for(int i = 0;i<len;i++) {
            if(i < len1) {
                arr[i] = nums1[i];
            }else {
                arr[i] = nums2[i-len1];
            }
        }
        // 排序新数组
        Arrays.sort(arr);
        double ret = 0;
        if(len%2==0) {
            ret = ((double)(arr[len/2] + arr[len/2-1]))/2;
        }else {
            ret = arr[len/2];
        }
        return ret;
    }
}
